<!DOCTYPE html>
<html lang="zh">
<head>
    <meta charset="UTF-8">
    <title>哈夫曼树可视化</title>
    <script src="https://cdn.jsdelivr.net/npm/d3@7"></script>
    <style>
        body { font-family: "微软雅黑", Arial, sans-serif; }
        .node circle { fill: #fff; stroke: steelblue; stroke-width: 2px; }
        .node text { font: 14px sans-serif; }
        .link { fill: none; stroke: #ccc; stroke-width: 2px; }
    </style>
</head>
<body>
    <h2>哈夫曼树可视化（D3.js）</h2>
    <textarea id="input" rows="8" cols="60" placeholder="在此输入字符及权值，每行一个，如：&#10;A 64&#10;B 13&#10;空格 186"></textarea><br>
    <button onclick="buildAndDraw()">生成哈夫曼树</button>
    <div id="tree"></div>
    <script>
        // 哈夫曼树节点定义
        class Node {
            constructor(ch, weight, left = null, right = null) {
                this.ch = ch;
                this.weight = weight;
                this.left = left;
                this.right = right;
            }
        }

        // 构建哈夫曼树
        function buildHuffmanTree(data) {
            let nodes = data.map(item => new Node(item.ch, item.weight));
            while (nodes.length > 1) {
                nodes.sort((a, b) => a.weight - b.weight);
                let left = nodes.shift();
                let right = nodes.shift();
                let parent = new Node('', left.weight + right.weight, left, right);
                nodes.push(parent);
            }
            return nodes[0];
        }

        // 转换为D3树结构
        function toD3Tree(node) {
            if (!node) return null;
            let name = node.ch ? (node.ch === ' ' ? '空格' : node.ch) + '(' + node.weight + ')' : '#' + '(' + node.weight + ')';
            let children = [];
            if (node.left) children.push(toD3Tree(node.left));
            if (node.right) children.push(toD3Tree(node.right));
            return children.length ? { name, children } : { name };
        }

        // 解析输入
        function parseInput(str) {
            let lines = str.trim().split('\n');
            let data = [];
            for (let line of lines) {
                let [ch, weight] = line.trim().split(/\s+/);
                if (ch === '空格') ch = ' ';
                if (!isNaN(weight)) data.push({ ch, weight: parseInt(weight) });
            }
            return data;
        }

        // 绘制树
        function drawTree(treeData) {
            document.getElementById('tree').innerHTML = '';
            const width = 900, height = 600;
            const svg = d3.select("#tree").append("svg")
                .attr("width", width)
                .attr("height", height);

            const g = svg.append("g").attr("transform", "translate(40,40)");

            const root = d3.hierarchy(treeData);
            const treeLayout = d3.tree().size([width - 100, height - 100]);
            treeLayout(root);

            // 连线
            g.selectAll('.link')
                .data(root.links())
                .enter()
                .append('path')
                .attr('class', 'link')
                .attr('d', d3.linkVertical()
                    .x(d => d.x)
                    .y(d => d.y)
                );

            // 节点
            const node = g.selectAll('.node')
                .data(root.descendants())
                .enter()
                .append('g')
                .attr('class', 'node')
                .attr('transform', d => `translate(${d.x},${d.y})`);

            node.append('circle').attr('r', 20);
            node.append('text')
                .attr('dy', 5)
                .attr('text-anchor', 'middle')
                .text(d => d.data.name);
        }

        // 主入口
        function buildAndDraw() {
            const input = document.getElementById('input').value;
            const data = parseInput(input);
            if (data.length < 2) {
                alert('请至少输入两个字符及权值！');
                return;
            }
            const root = buildHuffmanTree(data);
            const d3Tree = toD3Tree(root);
            drawTree(d3Tree);
        }
    </script>
</body>
</html>